// ms_grid_test_rand.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <signal.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <pthread.h>
#include <io.h>
#include <windows.h>

#define UPLEFT 0
#define UP 1
#define UPRIGHT 2
#define RIGHT 3
#define DOWNRIGHT 4
#define DOWN 5
#define DOWNLEFT 6
#define LEFT 7
#define USED 8

#define SAVEREQUIRED -1
#define BESTSCOREFOUND -2

struct line
{
	char x;
	char y;
	char pos;
	char dir;
};

char grid[60][60][9];//This is the table where the game is stored : 60*60 points, 0-7 : possibilities (directions see define), 8 : l empty or not
int searching_state[1000][4];//This table contains the state of the algorithm, it's used to save the progress of the search. Format : (current possibility | max possibility | best possibility | best score) for each floor of the tree
struct line selected_lines[1000];//This table contains the list of the lines played, it's large enough to contain the largest theoric game
struct line possibilities[400][100];//This table contains 100 possibilities for 400 floors max (large enough to contain the largest theoric game)
char searching_range[4] = {24, 35, 24, 35};//{min x, max x, min y, max y}
long long int max_possibility_score;
unsigned int accuracy = 1000;
int scoring_mode = 0;
int score = 0;
int current_searching_floor = 0;
int current_searching_pos = 0;
int current_searching_pos_nb = 4;
int target_score = 0;
int score_max = 0;
unsigned long long int games_nbr = 0;
unsigned long long int starting_games_nbr = 0;
int line_no = 0;
char name[100];
char name_suffix[100];
FILE *f = NULL;
int start_time = 0;
int checkpoint_time = 0;
unsigned long long int checkpoint_games_nbr = 0;
bool stop = false;
pthread_mutex_t save_mutex = NULL;

unsigned long long int pow10(int x)
{
	unsigned long long int r = 1;
	for (int i = 0 ; i < x ; i ++)
		r *= 10;
	return r;
}

void format(unsigned long long int nbr)
{
	char str[100];
	int pos = 0;
	int exponent = 0;
	unsigned long long int i = nbr;

	while (i != 0)
	{
		i /= 10;
		exponent ++;
	}
	//printf("\nnumber = %llu, exponent = %d\n", nbr, exponent);
	for (; exponent > 0 ; exponent --)
	{
		i = (nbr / pow10(exponent-1)) - ((nbr / pow10(exponent)) * 10);
		str[pos++] = i + 48;
		//printf("%d\n", i);
		if ((exponent-1) % 3 == 0)
		{
			str[pos++] = ',';
		}
	}
	str[--pos] = '\0';
	printf("%s", str);
	//system("pause");
}

void format(int nbr)
{
	char str[100];
	int pos = 0;
	int exponent = 0;
	int i = nbr;

	while (i != 0)
	{
		i /= 10;
		exponent ++;
	}

	for (; exponent > 0 ; exponent --)
	{
		i = (nbr / pow10(exponent-1)) - ((nbr / pow10(exponent)) * 10);
		str[pos++] = i + 48;
		if ((exponent-1) % 3 == 0)
		{
			str[pos++] = ',';
		}
	}
	str[--pos] = '\0';
	printf("%s", str);
}

void save(bool display, int save_score = -1)
{
	pthread_mutex_lock(&save_mutex);
	FILE *solved_game = NULL;
	int ssc;

	if (save_score != -1)
	{
		ssc = save_score;
		solved_game = fopen("save.txt", "w+");
	}
	else
	{
		ssc = current_searching_floor+1;
		solved_game = fopen("quick_save.txt", "w+");
	}
	
	fprintf(solved_game, "games_nbr = %llu\nscore_max = %d\ndeep = %d\ntarget_score = %d\naccuracy = %d\nscoring_mode = %d\n", games_nbr, score_max, ssc, target_score, accuracy, scoring_mode);

	for (int x = 0 ; x < ssc ; x ++)
	{
		fprintf(solved_game, "\n%d|%d|%d|%d", searching_state[x][0], searching_state[x][1], searching_state[x][2], searching_state[x][3]);
	}
	rewind(solved_game);
	fclose(solved_game);
	if (display)
		printf("\nThe backup was properly done !\n");
	//system("pause");
	pthread_mutex_unlock(&save_mutex);
}

BOOL CtrlHandler( DWORD fdwCtrlType )
{
	switch( fdwCtrlType )
	{
		case CTRL_C_EVENT:
			save(false);
			stop = true;
			return TRUE;
		case CTRL_BREAK_EVENT:
			save(true);
			return TRUE;
		default:
			return FALSE;
	}
}

int add_line(struct line l)
{
	int i, x, y;

	selected_lines[line_no].dir = l.dir;
	selected_lines[line_no].pos = l.pos;
	selected_lines[line_no].x = l.x;
	selected_lines[line_no].y = l.y;

	//printf("selected_lines added : (%d,%d) %d %d\n", l.x, l.y, l.dir, l.pos);
	line_no ++;
	grid[l.x][l.y][8] = 1;
	if (l.x == searching_range[0])//Increasing searching range if the added line is on the bounds
	{
		searching_range[0] --;
	}
	else if (l.x == searching_range[1])
	{
		searching_range[1] ++;
	}
	if (l.y == searching_range[2])
	{
		searching_range[2] --;
	}
	else if (l.y == searching_range[3])
	{
		searching_range[3] ++;
	}

	if (l.dir == 1)//Add an horizontal line (-)
	{
		grid[l.x - 2 + l.pos][l.y][3] = 1;
		for (i = (l.x - 1 + l.pos) ; i < (l.x + 2 + l.pos) ; i ++)
		{
			grid[i][l.y][3] = 1;
			grid[i][l.y][7] = 1;
		}
		grid[l.x + 2 + l.pos][l.y][7] = 1;
	}
	else if (l.dir == 2)//Add a vertical line (|)
	{
		grid[l.x][l.y - 2 + l.pos][5] = 1;
		for (i = (l.y - 1 + l.pos) ; i < (l.y + 2 + l.pos) ; i ++)
		{
			grid[l.x][i][5] = 1;
			grid[l.x][i][1] = 1;
		}
		grid[l.x][l.y + 2 + l.pos][1] = 1;
	}
	else if (l.dir == 3)//Add an oblique line (/)
	{
		x = (l.x - 2 + l.pos);
		grid[x][l.y + 2 - l.pos][2] = 1;
		x ++;
		for (y = (l.y + 1 - l.pos) ; y > (l.y - 2 - l.pos) ; y --)
		{
			grid[x][y][2] = 1;
			grid[x][y][6] = 1;
			x ++;
		}
		grid[x][l.y - 2 - l.pos][6] = 1;
	}
	else if (l.dir == 4)//Add an oblique line (\)
	{
		x = (l.x - 2 + l.pos);
		grid[x][l.y - 2 + l.pos][4] = 1;
		x ++;
		for (y = (l.y - 1 + l.pos) ; y < (l.y + 2 + l.pos) ; y ++)
		{
			grid[x][y][4] = 1;
			grid[x][y][0] = 1;
			x ++;
		}
		grid[x][l.y + 2 + l.pos][0] = 1;
	}
	return 0;
}

int remove_line()
{
	struct line l;
	int i, x, y;

	line_no --;
	l.dir = selected_lines[line_no].dir;
	l.pos = selected_lines[line_no].pos;
	l.x = selected_lines[line_no].x;
	l.y = selected_lines[line_no].y;
	
	selected_lines[line_no].x = 28;
	selected_lines[line_no].y = 28;
	//printf("selected_lines removed : (%d,%d) %d %d\n", l.x, l.y, l.dir, l.pos);
	grid[l.x][l.y][8] = 0;
	if (l.dir == 1)//Remove an horizontal line (-)
	{
		grid[l.x - 2 + l.pos][l.y][3] = 0;
		for (i = (l.x - 1 + l.pos) ; i < (l.x + 2 + l.pos) ; i ++)
		{
			grid[i][l.y][3] = 0;
			grid[i][l.y][7] = 0;
		}
		grid[l.x + 2 + l.pos][l.y][7] = 0;
	}
	else if (l.dir == 2)//Remove a vertical line (|)
	{
		grid[l.x][l.y - 2 + l.pos][5] = 0;
		for (i = (l.y - 1 + l.pos) ; i < (l.y + 2 + l.pos) ; i ++)
		{
			grid[l.x][i][5] = 0;
			grid[l.x][i][1] = 0;
		}
		grid[l.x][l.y + 2 + l.pos][1] = 0;
	}
	else if (l.dir == 3)//Remove an oblique line (/)
	{
		x = (l.x - 2 + l.pos);
		grid[x][l.y + 2 - l.pos][2] = 0;
		x ++;
		for (y = (l.y + 1 - l.pos) ; y > (l.y - 2 - l.pos) ; y --)
		{
			grid[x][y][2] = 0;
			grid[x][y][6] = 0;
			x ++;
		}
		grid[x][l.y - 2 - l.pos][6] = 0;
	}
	else if (l.dir == 4)//Remove an oblique line (\)
	{
		x = (l.x - 2 + l.pos);
		grid[x][l.y - 2 + l.pos][4] = 0;
		x ++;
		for (y = (l.y - 1 + l.pos) ; y < (l.y + 2 + l.pos) ; y ++)
		{
			grid[x][y][4] = 0;
			grid[x][y][0] = 0;
			x ++;
		}
		grid[x][l.y + 2 + l.pos][0] = 0;
	}
	return 0;
}

int possibilities_update()
{
	//possibilities update
	int i = 0;
	char x = 0;
	char y = 0;
	int no_pos = 0;
	bool add_pos = true;
	int floor = score;
	
	for (y = searching_range[2] ; y <= searching_range[3] ; y ++)//We test all the search field
	{
		for (x = searching_range[0] ; x <= searching_range[1] ; x ++)
		{
			if (grid[x][y][USED] == 0)//Dots that are in the search field and which are empty are may host to one or more possibilities
			{
				//Test horizontal 2
				if ((grid[x + 1][y][USED] == 1) && (grid[x + 2][y][USED] == 1) && (grid[x + 3][y][USED] == 1) && (grid[x + 4][y][USED] == 1) && (grid[x + 1][y][RIGHT] == 0) && (grid[x + 2][y][RIGHT] == 0) && (grid[x + 3][y][RIGHT] == 0) && (grid[x + 2][y][LEFT] == 0) && (grid[x + 3][y][LEFT] == 0) && (grid[x + 4][y][LEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 1;
					possibilities[floor][no_pos].pos = 2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test horizontal -2
				if ((grid[x - 1][y][USED] == 1) && (grid[x - 2][y][USED] == 1) && (grid[x - 3][y][USED] == 1) && (grid[x - 4][y][USED] == 1) && (grid[x - 1][y][LEFT] == 0) && (grid[x - 2][y][LEFT] == 0) && (grid[x - 3][y][LEFT] == 0) && (grid[x - 2][y][RIGHT] == 0) && (grid[x - 3][y][RIGHT] == 0) && (grid[x - 4][y][RIGHT] == 0))
				{
					possibilities[floor][no_pos].dir = 1;
					possibilities[floor][no_pos].pos = -2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test vertical 2
				if ((grid[x][y + 1][USED] == 1) && (grid[x][y + 2][USED] == 1) && (grid[x][y + 3][USED] == 1) && (grid[x][y + 4][USED] == 1) && (grid[x][y + 1][DOWN] == 0) && (grid[x][y + 2][DOWN] == 0) && (grid[x][y + 3][DOWN] == 0) && (grid[x][y + 2][UP] == 0) && (grid[x][y + 3][UP] == 0) && (grid[x][y + 4][UP] == 0))
				{
					possibilities[floor][no_pos].dir = 2;
					possibilities[floor][no_pos].pos = 2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test vertical -2
				if ((grid[x][y - 1][USED] == 1) && (grid[x][y - 2][USED] == 1) && (grid[x][y - 3][USED] == 1) && (grid[x][y - 4][USED] == 1) && (grid[x][y - 2][DOWN] == 0) && (grid[x][y - 3][DOWN] == 0) && (grid[x][y - 4][DOWN] == 0) && (grid[x][y - 1][UP] == 0) && (grid[x][y - 2][UP] == 0) && (grid[x][y - 3][UP] == 0))
				{
					possibilities[floor][no_pos].dir = 2;
					possibilities[floor][no_pos].pos = -2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test horizontal 1
				if ((grid[x - 1][y][USED] == 1) && (grid[x + 1][y][USED] == 1) && (grid[x + 2][y][USED] == 1) && (grid[x + 3][y][USED] == 1) && (grid[x + 1][y][RIGHT] == 0) && (grid[x + 2][y][RIGHT] == 0) && (grid[x + 2][y][LEFT] == 0) && (grid[x + 3][y][LEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 1;
					possibilities[floor][no_pos].pos = 1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test horizontal -1
				if ((grid[x - 3][y][USED] == 1) && (grid[x - 2][y][USED] == 1) && (grid[x - 1][y][USED] == 1) && (grid[x + 1][y][USED] == 1) && (grid[x - 1][y][LEFT] == 0) && (grid[x - 2][y][LEFT] == 0) && (grid[x - 2][y][RIGHT] == 0) && (grid[x - 3][y][RIGHT] == 0))
				{
					possibilities[floor][no_pos].dir = 1;
					possibilities[floor][no_pos].pos = -1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test vertical 1
				if ((grid[x][y - 1][USED] == 1) && (grid[x][y + 1][USED] == 1) && (grid[x][y + 2][USED] == 1) && (grid[x][y + 3][USED] == 1) && (grid[x][y + 1][DOWN] == 0) && (grid[x][y + 2][DOWN] == 0) && (grid[x][y + 2][UP] == 0) && (grid[x][y + 3][UP] == 0))
				{
					possibilities[floor][no_pos].dir = 2;
					possibilities[floor][no_pos].pos = 1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test vertical -1
				if ((grid[x][y + 1][USED] == 1) && (grid[x][y - 1][USED] == 1)&& (grid[x][y - 2][USED] == 1) && (grid[x][y - 3][USED] == 1) && (grid[x][y - 1][UP] == 0) && (grid[x][y - 2][UP] == 0) && (grid[x][y - 2][DOWN] == 0) && (grid[x][y - 3][DOWN] == 0))
				{
					possibilities[floor][no_pos].dir = 2;
					possibilities[floor][no_pos].pos = -1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test horizontal 0
				if ((grid[x - 2][y][USED] == 1) && (grid[x - 1][y][USED] == 1) && (grid[x + 1][y][USED] == 1) && (grid[x + 2][y][USED] == 1) && (grid[x - 2][y][RIGHT] == 0) && (grid[x - 1][y][LEFT] == 0) && (grid[x + 1][y][RIGHT] == 0) && (grid[x + 2][y][LEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 1;
					possibilities[floor][no_pos].pos = 0;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test vertical 0
				if ((grid[x][y - 2][USED] == 1) && (grid[x][y - 1][USED] == 1) && (grid[x][y + 1][USED] == 1) && (grid[x][y + 2][USED] == 1) && (grid[x][y - 2][DOWN] == 0) && (grid[x][y - 1][UP] == 0) && (grid[x][y + 1][DOWN] == 0) && (grid[x][y + 2][UP] == 0))
				{
					possibilities[floor][no_pos].dir = 2;
					possibilities[floor][no_pos].pos = 0;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test oblique1 2
				if ((grid[x + 1][y - 1][USED] == 1) && (grid[x + 2][y - 2][USED] == 1) && (grid[x + 3][y - 3][USED] == 1) && (grid[x + 4][y - 4][USED] == 1) && (grid[x + 1][y - 1][UPRIGHT] == 0) && (grid[x + 2][y - 2][UPRIGHT] == 0) && (grid[x + 3][y - 3][UPRIGHT] == 0) && (grid[x + 2][y - 2][DOWNLEFT] == 0) && (grid[x + 3][y - 3][DOWNLEFT] == 0) && (grid[x + 4][y - 4][DOWNLEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 3;
					possibilities[floor][no_pos].pos = 2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 -2
				if ((grid[x - 1][y + 1][USED] == 1) && (grid[x - 2][y + 2][USED] == 1) && (grid[x - 3][y + 3][USED] == 1) && (grid[x - 4][y + 4][USED] == 1) && (grid[x - 1][y + 1][DOWNLEFT] == 0) && (grid[x - 2][y + 2][DOWNLEFT] == 0) && (grid[x - 3][y + 3][DOWNLEFT] == 0) && (grid[x - 2][y + 2][UPRIGHT] == 0) && (grid[x - 3][y + 3][UPRIGHT] == 0) && (grid[x - 4][y + 4][UPRIGHT] == 0))
				{
					possibilities[floor][no_pos].dir = 3;
					possibilities[floor][no_pos].pos = -2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 1
				if ((grid[x - 1][y + 1][USED] == 1) && (grid[x + 1][y - 1][USED] == 1) && (grid[x + 2][y - 2][USED] == 1) && (grid[x + 3][y - 3][USED] == 1) && (grid[x + 1][y - 1][UPRIGHT] == 0) && (grid[x + 2][y - 2][UPRIGHT] == 0) && (grid[x + 2][y - 2][DOWNLEFT] == 0) && (grid[x + 3][y - 3][DOWNLEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 3;
					possibilities[floor][no_pos].pos = 1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 -1
				if ((grid[x - 3][y + 3][USED] == 1) && (grid[x - 2][y + 2][USED] == 1) && (grid[x - 1][y + 1][USED] == 1) && (grid[x + 1][y - 1][USED] == 1) && (grid[x - 1][y + 1][DOWNLEFT] == 0) && (grid[x - 2][y + 2][DOWNLEFT] == 0) && (grid[x - 2][y + 2][UPRIGHT] == 0) && (grid[x - 3][y + 3][UPRIGHT] == 0))
				{
					possibilities[floor][no_pos].dir = 3;
					possibilities[floor][no_pos].pos = -1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique1 0
				if ((grid[x - 2][y + 2][USED] == 1) && (grid[x - 1][y + 1][USED] == 1) && (grid[x + 1][y - 1][USED] == 1) && (grid[x + 2][y - 2][USED] == 1) && (grid[x - 2][y + 2][UPRIGHT] == 0) && (grid[x - 1][y + 1][DOWNLEFT] == 0) && (grid[x + 1][y - 1][UPRIGHT] == 0) && (grid[x + 2][y - 2][DOWNLEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 3;
					possibilities[floor][no_pos].pos = 0;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}

				//Test oblique2 2
				if ((grid[x + 1][y + 1][USED] == 1) && (grid[x + 2][y + 2][USED] == 1) && (grid[x + 3][y + 3][USED] == 1) && (grid[x + 4][y + 4][USED] == 1) && (grid[x + 1][y + 1][DOWNRIGHT] == 0) && (grid[x + 2][y + 2][DOWNRIGHT] == 0) && (grid[x + 3][y + 3][DOWNRIGHT] == 0) && (grid[x + 2][y + 2][UPLEFT] == 0) && (grid[x + 3][y + 3][UPLEFT] == 0) && (grid[x + 4][y + 4][UPLEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 4;
					possibilities[floor][no_pos].pos = 2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 -2
				if ((grid[x - 1][y - 1][USED] == 1) && (grid[x - 2][y - 2][USED] == 1) && (grid[x - 3][y - 3][USED] == 1) && (grid[x - 4][y - 4][USED] == 1)  && (grid[x - 1][y - 1][UPLEFT] == 0) && (grid[x - 2][y - 2][UPLEFT] == 0) && (grid[x - 3][y - 3][UPLEFT] == 0) && (grid[x - 2][y - 2][DOWNRIGHT] == 0) && (grid[x - 3][y - 3][DOWNRIGHT] == 0) && (grid[x - 4][y - 4][DOWNRIGHT] == 0))
				{
					possibilities[floor][no_pos].dir = 4;
					possibilities[floor][no_pos].pos = -2;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 1
				if ((grid[x - 1][y - 1][USED] == 1) && (grid[x + 1][y + 1][USED] == 1) && (grid[x + 2][y + 2][USED] == 1) && (grid[x + 3][y + 3][USED] == 1) && (grid[x + 1][y + 1][DOWNRIGHT] == 0) && (grid[x + 2][y + 2][DOWNRIGHT] == 0) && (grid[x + 2][y + 2][UPLEFT] == 0) && (grid[x + 3][y + 3][UPLEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 4;
					possibilities[floor][no_pos].pos = 1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 -1
				if ((grid[x - 3][y - 3][USED] == 1) && (grid[x - 2][y - 2][USED] == 1) && (grid[x - 1][y - 1][USED] == 1) && (grid[x + 1][y + 1][USED] == 1) && (grid[x - 3][y - 3][DOWNRIGHT] == 0) && (grid[x - 2][y - 2][DOWNRIGHT] == 0) && (grid[x - 2][y - 2][UPLEFT] == 0) && (grid[x - 1][y - 1][UPLEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 4;
					possibilities[floor][no_pos].pos = -1;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
				//Test oblique2 0
				if ((grid[x - 2][y - 2][USED] == 1) && (grid[x - 1][y - 1][USED] == 1) && (grid[x + 1][y + 1][USED] == 1) && (grid[x + 2][y + 2][USED] == 1) && (grid[x - 2][y - 2][DOWNRIGHT] == 0) && (grid[x - 1][y - 1][UPLEFT] == 0) && (grid[x + 1][y + 1][DOWNRIGHT] == 0) && (grid[x + 2][y + 2][UPLEFT] == 0))
				{
					possibilities[floor][no_pos].dir = 4;
					possibilities[floor][no_pos].pos = 0;
					possibilities[floor][no_pos].x = x;
					possibilities[floor][no_pos].y = y;
					no_pos ++;
				}
			}
		}
	}

	possibilities[floor][no_pos].x = 28;//End list mark
	possibilities[floor][no_pos].y = 28;

	return no_pos;//We return the number of possibilities
}

void new_game_found()
{
	games_nbr ++;
	if (score > score_max)//If the score becomes higher than the last best score, then the grid is saved in an file
	{
		score_max = score;
		printf("\r                                                                               \rNb games : ");
		format(games_nbr);
		printf(", A new best game was found, score : %d\n", score_max);

		char save_location[248];
		sprintf_s(save_location, "games");
		CreateDirectoryA((LPCSTR)&save_location, NULL);

		sprintf(name, "games/game_");
		sprintf(name_suffix, "%d", score_max);
		strcat(name, name_suffix);
		strcat(name, ".txt");
		f = fopen(name, "w+");
		fprintf(f, "# JEC2000's game\n#\n");
		fprintf(f, "# Score : %d\n(28,28)\n", score_max);
		int i = 0;
		while ((selected_lines[i].x != 28) || (selected_lines[i].y != 28))
		{
			if (selected_lines[i].dir == 1)
			{
				fprintf(f, "(%d,%d) - %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			else if (selected_lines[i].dir == 2)
			{
				fprintf(f, "(%d,%d) | %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			else if (selected_lines[i].dir == 3)
			{
				fprintf(f, "(%d,%d) / %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			else if (selected_lines[i].dir == 4)
			{
				fprintf(f, "(%d,%d) \\ %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			i ++;
		}
		rewind(f);
		fclose(f);
		save(false);
	}
	if ((GetTickCount() - checkpoint_time) >= 1000)//Shows every seconds the number of completed games and some info to the user
	{
		printf("\r                                                                               \rTested : ");
		format(games_nbr);
		printf(" floor %d (%d/%d) ", current_searching_floor+1, current_searching_pos+1, current_searching_pos_nb);
		if ((GetTickCount() - start_time) >= 1000)//We avoids a division by zero...
		{
			printf("speed (avg) : ");
			format((games_nbr - checkpoint_games_nbr) / (int)((GetTickCount() - checkpoint_time) / 1000));
			printf(" (");
			format((games_nbr - starting_games_nbr) / (int)((GetTickCount() - start_time) / 1000));
			printf(") games/sec");
		}
		checkpoint_games_nbr = games_nbr;
		checkpoint_time = GetTickCount();
	}
}

int random_tests(int no)//Second part of the algorithm, we do $accuracy random tests on the $no possibility 
{
	score++;
	int nb_pos;
	struct line l = possibilities[score - 1][no];
	int total_score = 0;

	pthread_mutex_lock(&save_mutex);//To stop search while we are saving...
	pthread_mutex_unlock(&save_mutex);
	if (stop)
		return SAVEREQUIRED;
	
	add_line(l);//We add to the game the corresponding line to the possibility "no"
	nb_pos = possibilities_update();//We must update possibilities after adding this line.

	if (nb_pos == 0)//If there is no more possibilities, then we've just completed a game
	{
		new_game_found();//A new game is found.
		if (score > target_score)//If we have exceeded the maximum score wanted by the user, then we exit the recursive search
			return BESTSCOREFOUND;
		else//Otherwise we remove the line that was added at the beginning of the function and we descend from one floor in the tree
		{
			remove_line();
			score --;
			return 0;
		}
	}

	searching_state[score][1] = nb_pos;//We updates the total number of possibilities of that floor
	int score_temp = score;//We save the score of this level
	int nb_pos_temp;
	int no_rand_pos;

	for (int nbt = 0 ; nbt < accuracy ; nbt ++)
	{
		srand (time(NULL) + nbt);
		no_rand_pos = rand() % nb_pos;//We choose the possibility

		if (stop)//To stop search while we are saving...
			return SAVEREQUIRED;

		do//We don't continue recursively now, this is too slow
		{
			score ++;
			add_line(possibilities[score - 1][no_rand_pos]);//We add to the game the corresponding line to the randomly choosen possibility
			nb_pos_temp = possibilities_update();//We must update possibilities after adding this line.

			if (nb_pos_temp == 0)//If there is no more possibilities, then we've just completed a game
			{
				if (scoring_mode == 0)//If scoring mode is the average score
					total_score += score;//We add the new score to the total score of the possibility
				else if (score > total_score)//If scoring mode is the maximum score
					total_score = score;//We store the new score in the max score of the possibility
				new_game_found();//A new game is found.
				if (score > target_score)//If we have exceeded the maximum score wanted by the user, then we exit the recursive search
					return BESTSCOREFOUND;
				else//Otherwise we remove all the lines that were added
				{
					for (; score > score_temp ; score --)
					{
						remove_line();
					}
					break;
				}
			}
			else
			{
				no_rand_pos = rand() % nb_pos_temp;//We choose the possibility of the next floor
			}
		}
		while (true);//While there is at least one possibility, we continue to add them.
	}

	searching_state[score][0] = -1;
	remove_line();
	score --;
	return total_score;
}

int resolution(int no)//first part of the algorithm, we do the research for each possibility
{
	score++;
	int i, x, nb_pos, result;
	struct line l = possibilities[score - 1][no];
	int total_score = 0;

	pthread_mutex_lock(&save_mutex);//To stop search while we are saving...
	pthread_mutex_unlock(&save_mutex);
	if (stop)
		return SAVEREQUIRED;
	
	add_line(l);//We add to the game the corresponding line to the possibility "no"
	nb_pos = possibilities_update();//We must update possibilities after adding this line.

	if (nb_pos == 0)//If there is no more possibilities, then we've just completed a game
	{
		new_game_found();//A new game is found.
		if (score > target_score)//If we have exceeded the maximum score wanted by the user, then we exit the recursive search
		{
			//printf("exit 1\n");
			return BESTSCOREFOUND;
		}
		else//Otherwise we remove the line that was added at the beginning of the function and we descend from one floor in the tree
		{
			//printf("exit 2\n");
			remove_line();
			score --;
			return 0;
		}
	}
	if ((searching_state[score][0] > 0) && (searching_state[score][0] <= nb_pos))//We must restore the progress of research after a backup
		x = searching_state[score][0] - 1;//So we continue where we stopped, with the possibility contained in the searching_state table (indexed between [0 and n-1] here and between [1 and n] for the backup therefore we subtract 1)
	else//Otherwise we starts searching from the first possibility (index 0)
		x = -1;

	searching_state[score][1] = nb_pos;//We updates the total number of possibilities of that floor

	current_searching_floor = score;
	current_searching_pos_nb = nb_pos;
	int temp_score;
	int best_pos = searching_state[score][2]-1;
	max_possibility_score = searching_state[score][3];

	if ((x == -1) || (best_pos != x))//We were testing the possibility x of n_pos and we found the best possibility at best_pos with a score of max_possibility_score
	{
		if (x == -1)
		{
			x = 0;
			best_pos = -1;
			max_possibility_score = -1;
		}
		//printf("\nTesting %d possibilities at floor %d\nstate : %d %d %d %d\n", nb_pos, score+1, searching_state[score][0]-1, searching_state[score][1], searching_state[score][2]-1, searching_state[score][3]);
		for (i = x ; i < nb_pos ; i ++)
		{
			current_searching_pos = i;
			searching_state[score][0] = i+1;
			temp_score = random_tests(i);//We test randomly the score of each possibility
			//printf("\nTested pos %d/%d : score : %d, (global score : %d)", i+1, nb_pos, temp_score, score);
			if (temp_score > max_possibility_score)
			{
				max_possibility_score = temp_score;
				best_pos = i;
				searching_state[score][2] = i+1;
				searching_state[score][3] = temp_score;
				//printf(" MAX SCORED !");
			}
			else if (temp_score == BESTSCOREFOUND)//If we found a game with a score greater or equal than requested, then we descend of a floor, else we continue to try the other possibilities
			{
				return BESTSCOREFOUND;
			}
			else if (temp_score == SAVEREQUIRED)//Backup has been requested in an upper floor
			{
				score --;
				return SAVEREQUIRED;
			}
			//printf("\n");
		}
		//system("pause");
	}

	if (best_pos == -1)
		return 0;//We stop if there are no more possibilities we don't actually need this because if we are here there are at least 1 possibility

	searching_state[score][0] = best_pos + 1;//We increment the state in searching_state to save it

	result = resolution(best_pos);//We go up from one floor in the tree with the possibility i and we increment the score

	if (result == BESTSCOREFOUND)//If we found a game with a score greater or equal than requested, then we descend of a floor, else we continue to try the other possibilities
		return BESTSCOREFOUND;
	else if (result == SAVEREQUIRED)//Backup has been requested in an upper floor
	{
		score --;
		return SAVEREQUIRED;
	}
	
	searching_state[score][0] = -1;
	remove_line();
	score --;
	return total_score;
}


int main(int argc, char* argv[])
{
	int i, x, y, a, b, c, d, result, nb_pos;
	FILE *solved_game = NULL;
	srand (time (NULL));
	for (i = 0 ; i < 1000 ; i ++)
	{
		searching_state[i][0] = -1;
		searching_state[i][1] = -1;
		searching_state[i][2] = 0;
		searching_state[i][3] = 0;
	}
	f = fopen("save.txt", "r+");
	if (f != NULL)
	{
		fscanf(f, "games_nbr = %llu\n", &games_nbr);
		starting_games_nbr = games_nbr;
		fscanf(f, "score_max = %d\n", &score_max);
		fscanf(f, "deep = %d\n", &x);
		fscanf(f, "target_score = %d\n", &target_score);
		fscanf(f, "accuracy = %d\n", &accuracy);
		fscanf(f, "scoring_mode = %d\n", &scoring_mode);
		for (i = 0 ; i < x ; i ++)
		{
			fscanf(f, "\n%d|%d|%d|%d", &a, &b, &c, &d);
			searching_state[i][0] = a;
			searching_state[i][1] = b;
			searching_state[i][2] = c;
			searching_state[i][3] = d;
			//printf("\n%d|%d|%d|%d", searching_state[i][0], searching_state[i][1], searching_state[i][2], searching_state[i][3]);
			if (a <= 0 || b <= 0 || a > b || b > CHAR_MAX || c < 0 || d < 0 || c > a)
			{
				printf("A reading error has occured.\nHave you modified the save.txt file ?\nProgram will now stop.\n");
				fclose(f);
				system("pause");
				return 0;
			}
			//printf("searching_state[%d] = [%d,%d]\n", i, searching_state[i][0], searching_state[i][1]);
		}
		//printf("searching_state[%d] = [%d,%d]\n", i, searching_state[i][0], searching_state[i][1]);
		fclose(f);
		printf("Morpion Solitaire by JEC2000\n\nSearch parameters :\nTarget score : %d\n", target_score);
		games_nbr --;
		printf("Number of games tested : ");
		format(games_nbr);
		printf("\nMaximum score reached : %d\n", score_max);

		printf("Accuracy : ");
		format((int)accuracy);
		printf(" random tests\n");

		if (scoring_mode == 0)
		{
			printf("Scoring possibility mode : average score\n");
		}
		else
		{
			printf("Scoring possibility mode : max score\n");
		}
	}
	else
	{
		printf("Morpion Solitaire by JEC2000\n\nEnter a target score (best known 178) : ");
		scanf("%d", &target_score);
		fflush(stdin);
		printf("\nEnter the number of random tests (>1) : ");
		scanf("%d", &accuracy);
		fflush(stdin);
		printf("\nEnter the scoring possibility mode (0 : average score, 1 : max score) : ");
		scanf("%d", &scoring_mode);
		fflush(stdin);
	}
	if (accuracy < 1)
		accuracy = 1;
	
	printf("\nPress CTRL+C to save and quit\n");
	printf("Press CTRL+BREAK to do a quick save and continue\n\n");
	//system("pause");

	HWND hConsole = GetConsoleWindow();
	HMENU hMenu = GetSystemMenu(hConsole, FALSE);
	DeleteMenu(hMenu, SC_CLOSE, MF_BYCOMMAND);//Disable the close cross button of the window

	SetConsoleCtrlHandler((PHANDLER_ROUTINE) CtrlHandler, TRUE);//Launches CtrlHandler function when receiving the signal CTRL+C or CTRL+BREAK
	pthread_mutex_init(&save_mutex, NULL);

	for (x = 0 ; x < 60 ; x ++)
	{
		for (y = 0 ; y < 60 ; y ++)
		{
			for (i = 0 ; i < 9 ; i ++)
			{
				grid[x][y][i] = 0;
			}
		}
	}

	for (i = 25 ; i < 29 ; i ++)
	{
		grid[i][28][8] = 1;
		grid[i][31][8] = 1;
		grid[i+3][25][8] = 1;
		grid[i+3][34][8] = 1;
		grid[i+6][28][8] = 1;
		grid[i+6][31][8] = 1;

		grid[28][i][8] = 1;
		grid[31][i][8] = 1;
		grid[25][i+3][8] = 1;
		grid[34][i+3][8] = 1;
		grid[28][i+6][8] = 1;
		grid[31][i+6][8] = 1;
	}

	for (i = 0 ; i < 1000 ; i ++)
	{
		selected_lines[i].dir = 0;
		selected_lines[i].pos = 0;
		selected_lines[i].x = 28;
		selected_lines[i].y = 28;
	}
	
	possibilities_update();
	nb_pos = 4;
	int root_pos[4] = {0,2,5,9};//We have only 4 true possibilities in the root because the others can be obtained by a symetry or a rotation of the game

	if ((searching_state[score][0] > 0) && (searching_state[score][0] <= nb_pos))//We must restore the progress of research after a backup
		x = searching_state[score][0] - 1;//So we continue where we stopped, with the possibility contained in the searching_state table (indexed between [0 and n-1] here and between [1 and n] for the backup therefore we subtract 1)
	else//Otherwise we starts searching from the first possibility (index 0)
		x = -1;

	searching_state[0][1] = nb_pos;
	start_time = GetTickCount();//We set the start time for displaying the speed of the algorithm
	checkpoint_games_nbr = starting_games_nbr;
	
	int temp_score;
	int best_pos = searching_state[0][2]-1;
	max_possibility_score = searching_state[0][3];
	//printf("\nTesting %d possibilities at floor %d\n", nb_pos, score);

	if ((x == -1) || (best_pos != x))//We were testing the possibility x of n_pos and we found the best possibility at best_pos with a score of max_possibility_score
	{
		if (x == -1)
		{
			x = 0;
			best_pos = -1;
			max_possibility_score = -1;
		}
		for (i = x ; i < nb_pos ; i ++)
		{
			current_searching_pos = i;
			searching_state[score][0] = i+1;
			temp_score = random_tests(root_pos[i]);//We test randomly the score of each possibility
			//printf("\nTested pos %d/%d : score : %d, (global score : %d)\n", i+1, nb_pos, temp_score, score);
			if (temp_score > max_possibility_score)
			{
				max_possibility_score = temp_score;
				best_pos = i;
				searching_state[score][2] = i+1;
				searching_state[score][3] = temp_score;
				//printf(" MAX SCORED !");
			}
			else if (temp_score == BESTSCOREFOUND)//If we found a game with a score greater or equal than requested, then we descend of a floor, else we continue to try the other possibilities
			{
				result = BESTSCOREFOUND;
				break;
			}
			else if (temp_score == SAVEREQUIRED)//Backup has been requested in an upper floor
			{
				score --;
				result = SAVEREQUIRED;
				break;
			}
			//printf("\n");
		}
	}

	if ((result != BESTSCOREFOUND) && (result != SAVEREQUIRED))
	{
		//printf("\nbest pos : %d\n", best_pos+1);
		searching_state[0][0] = best_pos + 1;//We increment the state in searching_state to save it
		result = resolution(root_pos[best_pos]);//We go up from one floor in the tree with the possibility root_pos[i] and we increment the score
	}

	if ((result != BESTSCOREFOUND) && (result != SAVEREQUIRED))
	{
		printf("\nSearch terminated !\nNo games were found with a score greater or equal than requested !\n");//Algorithm finished without finding any games with a score greater than or equal than requested
		result = -1;
	}
	else
	{
		//saving searching state
	
		i = 0;
		while (searching_state[i][0] != -1)
		{
			i ++;
		}

		save(true, i);
	}
	
	if (result == BESTSCOREFOUND)//We found a game with a score greater or equal to the required score, we save it
	{
		i = 0;
		solved_game = fopen("solved_game.txt", "w+");
		fprintf(solved_game, "# JEC2000's game\n#\n");
		fprintf(solved_game, "# Score : %d\n(28,28)\n", score);

		while ((selected_lines[i].x != 28) || (selected_lines[i].y != 28))
		{
			if (selected_lines[i].dir == 1)
			{
				fprintf(solved_game, "(%d,%d) - %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			else if (selected_lines[i].dir == 2)
			{
				fprintf(solved_game, "(%d,%d) | %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			else if (selected_lines[i].dir == 3)
			{
				fprintf(solved_game, "(%d,%d) / %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			else if (selected_lines[i].dir == 4)
			{
				fprintf(solved_game, "(%d,%d) \\ %d\n", selected_lines[i].x, selected_lines[i].y, selected_lines[i].pos);
			}
			i ++;
		}
		printf("A new game was found after %d games :\nScore : %d\n", games_nbr, score);
		rewind(solved_game);
		fclose(solved_game);
	}
	system("pause");
	pthread_mutex_destroy(&save_mutex);
	return 0;
}